Algorithmique - NSI
Algorithme glouton
Exercice 1 : Algorithme glouton et rendu de monnaie
Une caisse dispose des pièces et des billets suivants : 40;25;10;5;1.
On a autant de pièces et de billets que nécessaire.
Lors d'un achat, un caissier doit rendre 231 € à un client.
En utilisant l'algorithme glouton, compléter le tableau ci-dessous, qui répertorie les pièces et billets rendus par le caissier pour que le nombre d'éléments soit minimum :
Exercice 2 : Algorithme glouton et problème du sac à dos
- - La somme des poids des objets sélectionnés soit inférieure à 83 kg.
- - La somme des valeurs des objets sélectionnés soit la plus grande possible.
Exercice 3 : Algorithme glouton et rendu de monnaie
Une caisse dispose des pièces et des billets suivants : 75;40;25;2;1.
On a autant de pièces et de billets que nécessaire.
Lors d'un achat, un caissier doit rendre 166 € à un client.
En utilisant l'algorithme glouton, compléter le tableau ci-dessous, qui répertorie les pièces et billets rendus par le caissier pour que le nombre d'éléments soit minimum :
Exercice 4 : Algorithme glouton et problème du sac à dos
- - La somme des poids des objets sélectionnés soit inférieure à 4 kg.
- - La somme des valeurs des objets sélectionnés soit la plus grande possible.
Exercice 5 : Algorithme glouton et rendu de monnaie
Une caisse dispose des pièces et des billets suivants : 100;40;20;5;1.
On a autant de pièces et de billets que nécessaire.
Lors d'un achat, un caissier doit rendre 25 € à un client.
En utilisant l'algorithme glouton, compléter le tableau ci-dessous, qui répertorie les pièces et billets rendus par le caissier pour que le nombre d'éléments soit minimum :